



#include <iostream>
#include <vector>
using namespace std;

struct ListNode 
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

struct TreeNode 
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
 
using Node = ListNode;

class Solution
{
public:
    ListNode* partition1(ListNode* head, int x)
    {
        Node dummy(-200);
        dummy.next = head;
        Node* smaller = &dummy, * bigger = head;

        for (Node* prev = &dummy, *next = nullptr; bigger; )
        {
            if (bigger->val < x)
            {
                if (smaller->next == bigger)
                {
                    smaller = smaller->next;
                    prev = bigger;
                    bigger = bigger->next;
                }
                else
                {
                    next = bigger->next;

                    prev->next = next;
                    bigger->next = smaller->next;
                    smaller = smaller->next = bigger;
                    bigger = next;
                }
            }
            else
            {
                prev = bigger;
                bigger = bigger->next;
            }
        }
        // while (bigger)
        // {
        //     if (bigger->val < x)
        //     {
        //         smaller = smaller->next;
        //         swap(smaller->val, bigger->val);
        //     }
        //    bigger = bigger->next;
        // }

        return dummy.next;
    }

    ListNode* partition2(ListNode* head, int x)
    {
        Node dummy(-200), dummy1(-200), dummy2(-200);
        Node* smaller = &dummy1, * bigger = &dummy2;

        dummy.next = head;
        for (Node* cur = dummy.next; cur; cur = cur->next)
        {
            if (cur->val < x)
            {
                smaller->next = cur;
                smaller = smaller->next;
            }
            else
            {
                bigger->next = cur;
                bigger = bigger->next;
            }
        }
        smaller->next = dummy2.next;
        bigger->next = nullptr;

        return dummy1.next;
    }

    Node* GetList()
    {
        Node* node3 = new Node(3);
        Node* node1 = new Node(1);
        Node* node2 = new Node(2);

        node3->next = node1;
        node1->next = node2;

        return node3;
    }

    TreeNode* sortedArrayToBST(vector<int>& nums)
    {
        return _sortedArrayToBST(nums, 0, nums.size() - 1);
    }

private:
    TreeNode* _sortedArrayToBST(const vector<int>& nums, int lf, int rg)
    {
        if (lf > rg)
            return nullptr;

        int mid = lf + ((rg - lf) >> 1);
        TreeNode* cur = new TreeNode(nums[mid]);

        cur->left = _sortedArrayToBST(nums, lf, mid - 1);
        cur->right = _sortedArrayToBST(nums, mid + 1, rg);

        return cur;
    }
};

void Test1()
{
    Node* head = Solution().GetList();

    Solution().partition2(head, 3);
}

int main()
{
	Test1();

	return 0;
}